1. Field of the Invention
The present invention relates generally to parsing, and more particularly to determining a reverse path through a parse tree using information in a system configuration database.
2. Description of Related Art
Typically, when an operating system command is used to configure a router, a parser processes the command using a binary parse tree. The router is configured as specified in the operating system command based on information derived from the parsing. The data used to configure the router is stored in a system configuration database.
Frequently, it is necessary to access the information in the system configuration database and reconstruct the command or commands that were used to configure the router. This can be a formidable problem that requires significant time to execute.
As a demonstration of the problem, consider binary parse tree 100 of FIG. 1. Binary parse tree 100 typically was used in a router's operating system in processing configuration commands. At each of nodes 101 to 119, there can be zero, one, or two branches. The path that terminates at each of the end nodes of binary parse tree 100 represents a configuration state for the router. The particular configuration state obtained when the configuration command represented by binary parse tree 100 is executed is stored in the system configuration database.
To regenerate the original configuration command, the information in the system configuration database was used and each route through binary parse tree 100 was tested for validity. For simple binary parse tree 100, this could be done relatively quickly. However, the number of paths grows exponentially/geometrically with the number of tree layers and nodes. Consequently, the execution time required increased significantly as the commands became more complex. Unfortunately, given the system constraints in router hardware and the complicated configuration commands, improvements in the execution time would appear to require significant advances in router hardware performance.